//定义搜索二叉树的节点
template<class K>
class BSTreeNode
{
public:
    K _key;
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    BSTreeNode(const K& key)
    {
        _key = key;
        _left = nullptr;
        _right = nullptr;
    }
    ~BSTreeNode()
    {
        _left = nullptr;
        _right = nullptr;
    }
};

//定义搜索二叉树
template<class K>
class SearchBinaryTree
{
    typedef BSTreeNode<K> Node;  //重定义节点类型 
public:
    // 声明迭代器类为友元
    friend class iterator;
    bool Insert(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            parent = cur;
            if (key < cur->_key)
            {
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        cur=new Node(key);
        if(parent==nullptr)//如果父节点为空，说明树为空，直接插入3
        {
            _root=cur;
        }
        else if(key < parent->_key)
        {
            parent->_left=cur;
        }
        else
        {
            parent->_right=cur;
        }
        return true;
    }

    bool Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (key < cur->_key)//查找的值比当前节点的值小，说明在左子树
            {
                cur = cur->_left;
            }
            else if (key > cur->_key)//查找的值比当前节点的值大，说明在右子树
            {
                cur = cur->_right;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    bool Erase(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            parent = cur;
            if (key < cur->_key)
            {
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                cur = cur->_right;
            }
            else
            {
                break;
            } 
        }
        if (cur == nullptr)
        {
            return false;
        }

        // 1. 叶子节点
        if (cur->_left == nullptr && cur->_right == nullptr)
        {
            if (parent == nullptr)
            {
                _root = nullptr;
            }
            else if (parent->_left == cur)
            {
                parent->_left = nullptr;
            }
            else
            {
                parent->_right = nullptr;
            }
            delete cur;
        }
        // 2. 只有左子树
        else if (cur->_right == nullptr)
        {
            if (parent == nullptr)
            {
                _root = cur->_left;
            }
            else if (parent->_left == cur)
            {
                parent->_left = cur->_left;
            }
            else
            {
                parent->_right = cur->_left;
            }
            delete cur;
        }
        // 3. 只有右子树
        else if (cur->_left == nullptr)
        {
            if (parent == nullptr)
            {
                _root = cur->_right;
            }
            else if (parent->_left == cur)
            {
                parent->_left = cur->_right;
            }
            else
            {
                parent->_right = cur->_right;
            }
            delete cur;
        }
        // 4. 左右子树都有
        else
        {
            Node* minRight = cur->_right;
            Node* minRightParent = cur;
            while (minRight->_left)
            {
                minRightParent = minRight;
                minRight = minRight->_left;
            }
            cur->_key = minRight->_key;
            if (minRightParent->_left == minRight)
            {
                minRightParent->_left = minRight->_right;
            }
            else
            {
                minRightParent->_right = minRight->_right;
            }
            delete minRight;
        }
        return true;
    }
     
    // 迭代器实现
    class iterator
    {
    public:
        typedef BSTreeNode<K> Node;
        iterator(Node* node, SearchBinaryTree* tree)
            : _node(node), _tree(tree)
        {}

        K& operator*()
        {
            return _node->_key;
        }

        K* operator->()
        {
            return &_node->_key;
        }

        bool operator!=(const iterator& it)
        {
            return _node != it._node;
        }

        // 中序遍历的迭代器++操作
        iterator& operator++()
        {
            if (_node->_right)
            {
                // 有右子树，找右子树的最左节点
                Node* cur = _node->_right;
                while (cur->_left)
                {
                    cur = cur->_left;
                }
                _node = cur;
            }
            else
            {
                // 无右子树，找第一个祖先节点，该节点是其父节点的左子节点
                _node = FindNext(_node->_key);
            }
            return *this;
        }

    private:
        Node* _node;
        SearchBinaryTree* _tree; // 指向树的指针

        // 辅助函数：查找中序遍历的下一个节点
        Node* FindNext(const K& key)
        {
            Node* result = nullptr;
            Node* cur = _tree->_root;
            while (cur)
            {
                if (cur->_key > key)
                {
                    result = cur;
                    cur = cur->_left;
                }
                else
                {
                    cur = cur->_right;
                }
            }
            return result;
        }
    };

    iterator begin()
    {
        // 找最左节点
        Node* cur = _root;
        while (cur && cur->_left)
        {
            cur = cur->_left;
        }
        return iterator(cur, this);
    }

    iterator end()
    {
        return iterator(nullptr, this);
    }

private:
    Node* _root=nullptr;
};


#include <iostream>
using namespace std;


int main()
{
    SearchBinaryTree<int> sbt;
    sbt.Insert(10);
    sbt.Insert(5);
    sbt.Insert(15);
    sbt.Insert(3);
    sbt.Insert(7);
    sbt.Insert(12);
    sbt.Insert(17);
    sbt.Insert(2);
    sbt.Insert(4);
    sbt.Insert(6);
    sbt.Insert(8);
    sbt.Insert(11);
    sbt.Insert(13);
    sbt.Insert(16);
    sbt.Erase(10);
    sbt.Find(10);
    sbt.Find(15);
    sbt.Find(17);
    sbt.Find(2);
    sbt.Find(4);
    sbt.Find(6);
    sbt.Find(8);
    sbt.Find(11);
    sbt.Find(13);
    sbt.Find(16);
    sbt.Find(17);
    sbt.Find(2);
    sbt.Find(4);
    for(auto& i:sbt)
    {
        cout<<i<<" ";
    }
    cout<<endl;



    return 0;
}